// NC128 [双指针]接雨水问题
// https://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f
// 1.检查数组是否为空的特殊情况
// 2.准备双指针，分别指向数组首尾元素，代表最初的两个边界
// 3.指针往中间遍历，遇到更低柱子就是底，用较短的边界减去底就是这一列的接水量，遇到更高的柱子就是新的边界，更新边界大小。

//[3,1,2,5,2,4]
// 2

#include <algorithm>
#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;

class Solution {
 public:
  long long maxWater(const vector<int>& arr) {
    // write code here
    if (arr.size() <= 2) {
      return 0;
    }
    int left = 0;
    int right = arr.size() - 1;
    int maxLeft = arr[left];
    int maxRight = arr[right];
    int res = 0;
    while (left < right) {
      maxLeft = max(maxLeft, arr[left]);
      maxRight = max(maxRight, arr[right]);
      if (maxLeft < maxRight) {
        res += (maxLeft - arr[left++]);
      } else {
        res += (maxRight - arr[right--]);
      }
    }
    return res;
  }
};

int main_water() {
  vector<int> arr = {3, 1, 2, 5, 2, 4};
  Solution sol;
  long long res = sol.maxWater(arr);
  printf("%d\n", res);
  return 0;
}
